package com.springboot.prac.prac_leecode.lee01;

import java.util.*;

/**
 * @author : syl
 * @date : 2022/9/5 16:19
 * @desc : 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。
 * 题目链接：https://leetcode.cn/problems/two-sum/
 */
public class LeeCode_01 {
    public static void main(String[] args) {
        Integer[] nums = new Integer[100000];
        List<Integer> arrayList = new ArrayList();
        for (int i = 1; i < 100001; i++) {
            arrayList.add(i);
        }
        nums = arrayList.toArray(nums);
        System.out.println(nums.toString());
        Integer target = 199999;

        method01(nums, target);
        method02(nums, target);
    }

    /**
     * 常规解决方法-双重for循环
     * @param nums
     * @param target
     */
    public static void method01(Integer[] nums, Integer target) {
        long start = System.currentTimeMillis();
        System.out.println("开始");
        // 双循环遍历
        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j < nums.length; j++) {
                if (Objects.equals(nums[i] + nums[j], target)) {
                    System.out.println("i=" + i + ",j=" + j);
                    long end = System.currentTimeMillis();
                    System.out.println("结束, " + (end - start) + "ms");
                    return;
                }
            }
        }
    }

    /**
     * 优化 将数组转为map集合， 数组数值作为map的key，数组下标作为map的value
     * @param nums
     * @param target
     */
    public static void method02(Integer[] nums, Integer target) {
        System.out.println("开始");
        long start = System.currentTimeMillis();
        // 优化 假设数组中的数值都不重复,将数组转为map集合， 数值为key，位置为value
        Map<Integer, Integer> map = intToMap(nums);
        for (int i = 0; i < nums.length; i++) {
            if (Objects.nonNull(map.get(target - nums[i])) && !Objects.equals(map.get(target - nums[i]), i)) {
                System.out.println("i=" + i + ",j=" + map.get(target - nums[i]));
                long end = System.currentTimeMillis();
                System.out.println("结束, " + (end - start) + "ms");
                return;
            }
        }
    }


    /**
     * 数组 转成 map形式
     *
     * @param array 被操作数组
     * @return 目标Map
     */
    public static Map<Integer, Integer> intToMap(Integer[] array) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            map.putIfAbsent(array[i], i);
        }

        return map;
    }
}
